package com.es.heap;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 二十
 * @since 2022/1/18 8:52 上午
 */
public class MaxHeap<E extends Comparable<E>> extends AbstractMaxHeap<E> {

    private List<E> data;

    public MaxHeap() {
        data = new LinkedList<>();
    }

    /**
     * 将传入的数组构建成一个最大堆
     * Heapify:思想：将数组元素层序排列成一颗树，找到最后一个非叶子节点开始第一个节点 downElement。
     *  如何找到最后一个非叶子节点？最后一个节点的父节点
     * @param arr
     */
    public MaxHeap(E[] arr) {
        data = new LinkedList<>();
        data.addAll(Arrays.asList(arr));
        for (int i = getParent(arr.length - 1); i >=0; i--) {
            siftDown(i);
        }
    }

    @Override
    public boolean isEmpty() {
        return data.size() == 0;
    }

    @Override
    public int getSize() {
        return data.size();
    }

    /**
     * 求一个节点的父亲节点索引位置
     *
     * @return
     */
    @Override
    public int getParent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("no parent!");
        }
        return (index - 1) / 2;
    }

    /**
     * 求一个节点的左子节点
     */
    @Override
    public int getLeftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 求一个节点的右子节点
     */
    @Override
    public int getRightChild(int index) {
        return index * 2 + 2;
    }

    @Override
    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    /**
     * 当添加一个元素以后，可能堆中部分元素不再满足
     * 【堆中某个节点的值总是不大于其父节点的值】
     * 这个时候，需要对新添加的元素位置进行调整，交换他与他父节点的位置，如果交换以后仍不满足，还需要继续往上交换。
     */
    private void siftUp(int index) {

        while (index > 0 && data.get(getParent(index)).compareTo(data.get(index)) < 0) {
            swap(getParent(index), index);
            index = getParent(index);
        }
    }

    /**
     * 交换集合中两个位置的元素
     *
     * @param p
     * @param q
     */
    private void swap(int p, int q) {
        E e = data.get(p);
        data.set(p, data.get(q));
        data.set(q, e);
    }

    /**
     * 查找堆中的最大元素
     *
     * @return
     */
    @Override
    public E findMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("empty heap!");
        }
        return data.get(0);
    }

    /**
     * 删除堆中最大元素
     *
     * @return
     */
    @Override
    public E deleteMax() {
        E max = findMax();
        swap(0, getSize() - 1);
        data.remove(data.size() - 1);
        siftDown(0);
        return max;
    }

    /**
     * 下沉
     *
     * @param index
     */
    private void siftDown(int index) {

        while (getLeftChild(index) < data.size()) {
            int tmp = getLeftChild(index);
            if (getRightChild(index) < data.size() &&
                    data.get(getRightChild(index)).compareTo(data.get(getLeftChild(index))) > 0) {
                tmp = getRightChild(index);
            }
            if (data.get(index).compareTo(data.get(tmp)) > 0) {
                break;
            }
            swap(index, tmp);
            index = tmp;
        }
    }

    /**
     * 取出最大元素后，放入一个新元素
     *
     * @return
     */
    @Override
    public E replace(E e) {
        E max = findMax();
        data.set(0, e);
        siftDown(0);
        return max;
    }
}
